#!/usr/bin/env python
# -*- coding: utf-8 -*-

import pydoc
import sys
import time

"""
Este módulo contêm funções que implementam vários algoritmos para a criação de uma kd-tree e a sua "manutenção"
"""

__author__= "Jaime Machado"
__credits__= ["Jasnau Caeiro", "Joao Cardeira", "Miguel Silva"]

__license__ = "Apache License 2.0"
__version__= "1.0"
__date__ = "08-Julho-2012"
__maintainer__ = "Jaime Machado"
__email__ = "jslmestig@gmail.com"
__status__ = "Desenvolvimento"

sys.setrecursionlimit(100000)
#Contador para saber a posiçao do array a ordenar quando for o quicksort (x,y,z)
contador = 0

class No:
	def __init__(self,value):
		"""
		Construtor da classe No.
		Recebe um parâmetro (value = tuple de k dimensoes)
		O atributo key é o valor mais próximo da mediana
		"""
		
		self.key = None
		self.value = value

		self.parent = None
		self.left = None
		self.right = None
		self.depth = None	
	pass
	
class ArvoreKd:
	"""
	Construtor da classe arvóre
	Raiz da arvore é um No
	"""
	def __init__(self):
		root = No(None)
		
	
	def buildKdTree(self,nodeList,depth,v):
		"""
		Função para construir a Kd-Tree
		Recebe uma lista de nós e a profundidade da arvore por parametro
		Recebe tambem um Nó v o qual serve para atribuir o No.parent
		Utiliza a variável global contador
		Define uma lista de nós a esquerda do Nó e uma lista de nós à direita consoante a mediana.
		Utiliza o algortimos quicksort
		Cria uma lista de nós a esquerda e uma lista de nós a direita do Nó(mediana)
		Node.key é o valor mais próximo maior ou igual que o valor da mediana
		"""
		
		global contador
		nodeListLeft = []
		nodeListRight = []	

		"""
		Quando acaba de desenhar a sub-arvore esquerda, vai desenhar a sub-arvore direita.
		"""
		if len(nodeList) == 1:
			nodeList[0].parent = v
			nodeList[0].key = nodeList[0].value[contador]
			contador = 1
			return  nodeList[0]
		elif len(nodeList) == 0:

			return None
		nodeList = self.quicksort(nodeList,0,len(nodeList)-1)
		node = self.median(nodeList)
		node.key = node.value[contador]
		subsets = self.separate(nodeList,node)
		nodeListLeft = subsets[0]
		nodeListRight = subsets[1]

		if(v != None):
			node.parent = v
		"""
		Se o contador for igual a 2 voltar a 0 para analisar o x novamente.
		"""
		if contador == (len(nodeList[0].value))-1:
			contador = 0
		else:
			contador +=1		
		"""
		Construção da kd-tree Recursivamente		
		"""
		node.left = self.buildKdTree(nodeListLeft, depth + 1,node)
		node.right = self.buildKdTree(nodeListRight, depth + 1,node)

		return node

	
	def insert(self, z):
		"""
		Inserir nó na arvore
		Recebe como parametro o nó a inserir
		O código é baseado no pseudocódigo da página 294 do livro da disciplina
		É implementado um contador para saber qual a posiçao do tuple que é analisado para a inserção
		"""
		contador = 0
		y = None
		x = self.root
        	while x != None:
			y = x
			if z.value[contador] < x.key:
				x = x.left
			else:
				x = x.right
			if contador == (len(z.value))-1:
				contador = 0
			else:
				contador +=1		

		if contador < (len(z.value))-1:
			z.key = z.value[contador+1]
		else:
			z.key = z.value[0]

		z.parent = y


		if y == None:
			self.root = z
		elif z.value[contador] < y.key:
			y.left = z
		else:
			y.right = z
		return y.value
		
	
	def transplant(self, u, v):
		"""
		Método baseado no pseudocódigo da disciplina
		Recebe como parâmetros No u é o nó a ser substituido e o v é o nó a ser posto nessa posição		
		"""
		if u.parent == None:
			self.root = v
		elif u == u.parent.left:
			u.parent.left = v
		else:
			u.parent.right = v
		if v != None:
			v.parent = u.parent
	
	def delete(self, z):
		"""
		Metodo baseado no pseudocódigo do livro da disciplina
		Recebe como parametro um objecto No a ser removido
		"""
		if z.left == None:
			self.transplant(z, z.right)
		elif z.right == None:
			self.transplant(z, z.left)
	        else:
			y = self.minimum(z.right)
			if y.parent != z:
				self.transplant(y, y.right)
				y.right = z.right
				y.right.parent = y
			self.transplant(z, y)
			y.left = z.left
			y.left.parent = y
		return z.value
		
	def searchKdTree(self, point, tree, contador):
		"""
		Entrada: Escalar A, Escalar B e a raiz de uma sub-arvore da kd-tree
		Saida: Todos os pontos com as folhas abaixo de v que esteja dentro do alcance
		"""
		if tree is None:
			return "Não está na arvore o ponto que procura"

		if cmp(tree.value,point) == 0:
			return tree.value
		
		meanValue = tree.key
		if point[contador] < meanValue:
			subTree = tree.left	
		else:
			subTree = tree.right

		if cmp(contador,len(tree.value)-1) ==0:	
			contador = -1
		
		return self.searchKdTree(point,subTree,contador+1)
		
	

	def separate(self, nodeList, node):
		"""
		Método para a criação de duas listas segundo a mediana.
		Recebe como parametros uma lista de nós
		"""
		global contador
		leftSub = []
		rightSub = []
		
		for v in nodeList:
			if v.value[contador] < node.value[contador]:
				leftSub.append(v)
			elif v.value[contador] > node.value[contador]:
				rightSub.append(v)
		return (leftSub, rightSub)
	
	
	def median(self,A):
		"""
		Método para calcular a mediana de uma lista
		Vê se é par ou impar e retorna o nó
		"""
		node = None
		if (len(A))%2 == 0:
			medianValue = (A[((len(A)-1)/2)].value[contador] + A[len(A)/2].value[contador])/2
			while node == None:
				for v in A:
					if medianValue < v.value[contador]:
						node = v
						break
		else:
			medianValue = ((len(A)+1)/2) - 1
			node = A[medianValue]
		return node
	
	def minimum(self, x):
		"""
		Para determinar o minimo, aplicado o pseudocódigo do livro
		Parametro x é o nó dado a partir do qual queremos chegar ao minimo.
		"""
		while x.left != None:
		    x = x.left
		return x

	def quicksort(self,A,p,r):

		"""
		O algoritmo quicksort é utilizado para ordenar os valores de K a cada andar.
		@param A é o array a ser organizador
		@p é o pivot
		@r é o último elemento do array
		"""
		if p < r:
			q = self.partition(A,p,r)
			self.quicksort(A,p,q - 1)
			self.quicksort(A,q + 1,r)
		return A	
	def partition(self,A,p,r):
		"""
		Faz parte do algoritmos do quicksort
		"""
		global contador
		x = A[r].value[contador]
		i = p - 1
		j = p
		while j <= (r-1):
			if A[j].value[contador] <= x:
				i += 1
				A[i], A[j] = A[j], A[i]
			j += 1
		A[i + 1], A[r] = A[r], A[i + 1]
		return i + 1
		
	
	def print_node(self, node , depth, s):
	"""
	Metodo que imprime a árvore
	"""
                s = depth*" " + str(node.value) + "\n"
		
                if node.left != None:

                	s += "esq"
                        s += self.print_node(node.left, depth + 1, s)
                if node.right != None:

                	s += "dir"
                        s += self.print_node(node.right, depth + 1, s)
                return s
	                      
        def print_tree(self):
	"""
	Método que chama o metodo para imprimir a arvore
	""" 
                print self.print_node(self.root, 0, "")
	pass		
	
	
#Criação do array que irá conter os nós da arvore
Nos = [None for k in range(2000)]


for i in range(2000):
	Nos[i] = No((i,i+1,i+2))

arv = ArvoreKd()
start = time.time()
arv.root = arv.buildKdTree(Nos,0,None)
elapsed = (time.time() - start)
print "Fazer a arvore demorou.... ", elapsed


start = time.time()
print "Resultado da Procura: ", arv.searchKdTree((220,221,222),arv.root,0)
elapsed = (time.time() - start)

print "A procura demorou.... ", elapsed

Nos.append(No((95,37,51)))
start = time.time()
print "Inserted Value ", Nos[len(Nos)-1].value, "On node" ,arv.insert(Nos[len(Nos)-1])
elapsed = (time.time() - start)

print "A Inserção demorou.... ", elapsed

start = time.time()
print "Deleted Tree ", arv.delete(Nos[57])
elapsed = (time.time() - start)

print "Apagar o Nó demorou.... ", elapsed


#------------------------------
#Descomentar para imprimir a arvore

#arv.print_tree()

#------------------------------






